package com.leetcode.algorithm.y22.m06;

/**
 * 377. 组合总和 Ⅳ
 * 
 * https://leetcode.cn/problems/combination-sum-iv/
 * 
 * @author jie.deng
 *
 */
class Question0377Solution01 {
	
	public int combinationSum4(int[] nums, int target) {
		int len = nums.length;

		// DP状态定义
		int[] dp = new int[target + 1];

		// DP状态初始化
		dp[0] = 1;

		// DP状态转移方程
		for (int i = 1; i <= target; i++) {
			for (int j = 0; j < len; j++) {
				if (i - nums[j] >= 0) {
					dp[i] += dp[i - nums[j]];
				}
			}
		}
		return dp[target];
	}
    
}